#include <stdio.h>
#include <stdlib.h>
#include "fatal.h"

typedef int ElementType;
typedef ElementType ItemType[ 2 ];

struct KdNode;
typedef struct KdNode *Position;
typedef struct KdNode *KdTree;

struct KdNode
{
    ItemType Data;
    KdTree   Left;
    KdTree   Right;
};

/* START: fig12_43.txt */
static KdTree
RecursiveInsert( ItemType Item, KdTree T, int Level )
{
    if( T == NULL )
    {
        T = malloc( sizeof( struct KdNode ) );
        if( T == NULL )
            FatalError( "Out of space!!!" );
        T->Left = T->Right = NULL;
        T->Data[ 0 ] = Item[ 0 ];
        T->Data[ 1 ] = Item[ 1 ];
    }
    else
    if( Item[ Level ] < T->Data[ Level ] )
        T->Left = RecursiveInsert( Item, T->Left, !Level );
    else
        T->Right = RecursiveInsert( Item, T->Right, !Level );
    return T;
}

KdTree
Insert( ItemType Item, KdTree T )
{
    return RecursiveInsert( Item, T, 0 );
}
/* END */

/* START: fig12_44.txt */
/* Print items satisfying */
/* Low[ 0 ] <= Item[ 0 ] <= High[ 0 ] and */
/* Low[ 1 ] <= Item[ 1 ] <= High[ 1 ] */

static void
RecPrintRange( ItemType Low, ItemType High,
               KdTree T, int Level )
{
    if( T != NULL )
    {
        if( Low[ 0 ] <= T->Data[ 0 ] &&
                        T->Data[ 0 ] <= High[ 0 ] &&
                        Low[ 1 ] <= T->Data[ 1 ] &&
                        T->Data[ 1 ] <= High[ 1 ] )
            printf( "(%d,%d)\n",
                        T->Data[ 0 ], T->Data[ 1 ] );

        if( Low[ Level ] <= T->Data[ Level ] )
            RecPrintRange( Low, High, T->Left, !Level );
        if( High[ Level ] >= T->Data[ Level ] )
            RecPrintRange( Low, High, T->Right, !Level );
    }
}

void
PrintRange( ItemType Low, ItemType High, KdTree T )
{
    RecPrintRange( Low, High, T, 0 );
}
/* END */

main( )
{
    KdTree T;
    ItemType It, L, H;
    int i;

    printf( "Starting program\n" );

    T = NULL;
    for( i = 300; i < 370; i++ )
    {
        It[ 0 ] = i; It[ 1 ] = 2500 - i;
        T = Insert( It, T );
    }

    printf( "Insertions complete\n" );

    i = 1;
    L[ 0 ] = 70; L[ 1 ] = 2186; H[ 0 ] = 1200; H[ 1 ] = 2200;
    PrintRange( L, H, T );

    printf( "Done...\n" ) ;
    return 0;
}

